package tree.二叉树的最近公共祖先;


import java.util.ArrayList;
import java.util.List;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }

    @Override
    public int hashCode() {
        return super.hashCode();
    }

    @Override
    public boolean equals(Object obj) {
        if (this == null && obj == null) {
            return true;
        }
        if (this == null || obj == null) {
            return false;
        }
        if (obj == TreeNode.class) {
            return false;
        }
        TreeNode treeNode = (TreeNode) obj;
        return this.val == treeNode.val;
    }
}

public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        /**
         * 二叉树内节点不重复
         * 分别从root的左右递归查找找 p , q ，都找到了则证明 p q 分布在该节点两侧 ，未都找到则说明 p q为上下级,则返回p或q（看哪一个先找到）
         */
        if (root == null || root == p || root == q) {
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left != null && right != null) {
            return root;
        }
        return left == null ? right : left;

    }


    public static void main(String[] args) {
        Solution solution = new Solution();
        TreeNode treeNode = new TreeNode(2);
        TreeNode treeNode1 = new TreeNode(1);
        treeNode.left = null;
        treeNode.right = treeNode1;
        TreeNode treeNode2 = solution.lowestCommonAncestor(treeNode, treeNode, treeNode1);
        System.out.println(treeNode2);
    }
}
